package com.LeetCode.dp.String;

import org.junit.Test;

import java.util.Stack;

/**
 * 最长合法括号子串
 *
 * 维护一个栈，里面保存'('的下标，每次进入一个')'时，栈弹出，ans更新为当前扫描的下标
 * 与栈顶元素之间的距离(因为中间可能有些括号已经被消掉了)，因为栈可能为空，所以需要
 * 记录下起始记录点last。
 */
public class longestValidParentheses {

    /**
     *
     * @param s string字符串
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        Stack<Integer> stack = new Stack<>();
        int len = s.length();
        char[] chars = s.toCharArray();
        int ans = 0, last = -1;
        for(int i = 0; i<len; i++){
            if(chars[i] == '(')
                stack.push(i);
            else if(chars[i] == ')'){
                if(stack.isEmpty()) last = i;
                else{
                    stack.pop();
                    if(!stack.isEmpty()) ans = Math.max(ans, i - stack.peek());
                    else ans = Math.max(ans, i - last);
                }
            }
        }
        return ans;
    }


    @Test
    public void test(){
        System.out.println(longestValidParentheses("((()())"));
    }
}
